package com.hjr.leetcode.question100;

import com.hjr.leetcode.util.entity.ListNode;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 *23. 合并 K 个升序链表
 * 给你一个链表数组，每个链表都已经按升序排列。
 *
 * 请你将所有链表合并到一个升序链表中，返回合并后的链表。
 */
public class q23 {

    public static void main(String[] args) {
        ListNode listNode = mergeKListsP(new ListNode[]{new ListNode(-2, new ListNode(-1, new ListNode(-1, new ListNode(-1)))), new ListNode()});
        System.out.println(listNode.toStr());

    }

    // 203ms 43mb
    public static ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        if (lists.length == 1){
            return lists[0];
        }

        ListNode pre = new ListNode(0);
        ListNode head = pre;

        int index = hasNext(lists);

        while (index > -1) {
            int max = Integer.MAX_VALUE;
            int tempIndex = -1;
            for (int i = 0; i < lists.length; i++) {
                if (lists[i] != null && lists[i].val < max) {
                    max = lists[i].val;
                    tempIndex = i;
                }
            }

            if (tempIndex > -1){
                lists[tempIndex] = lists[tempIndex].next;
                head.next = new ListNode(max);
                head = head.next;
                index = hasNext(lists);
            }
        }

        return pre.next;
    }

    private static int hasNext(ListNode[] lists) {
        for (int i = 0; i < lists.length; i++) {
            if (lists[i] != null){
                return i;
            }
        }
        return -1;
    }

    //这段逻辑过不了提交，因为参数有个new ListNode导致java默认为0
    public static ListNode mergeKListsP(ListNode[] lists) {
        PriorityQueue<ListNode> listNodes = new PriorityQueue<>(Comparator.comparing(node -> node.val));
        for (ListNode listNode : lists) {
            while (listNode != null) {
                listNodes.add(listNode);
                listNode = listNode.next;
            }
        }

        ListNode pre = new ListNode(0);
        ListNode head = pre;
        while (!listNodes.isEmpty()) {
            head.next = listNodes.poll();
            head = head.next;
        }
        head.next = null;
        return pre.next;
    }

}
